// this is a draft of pseudo code to show the algorithm


#include <iostream>
#include <string>
#include <vector>
#include <map>
#include <list>
#include <set>
#include <deque>
#include <algorithm>
using namespace std;

struct node
{
	list<node*> getAdjs();
};

list<node*> getPath(node* from, node* to)
{
	set<node*> open;
	set<node*> closed;
	map<node*, node*> prev; // path

	map<node*, int> g; // h, 
#define h(x) 0
#define f(x) (g[(x)]+h(x)) // well, use g directly

	g[from]=0;

	open.insert(from);
	while(!open.empty())
	{
		node* pn=0;
		for(set<node*>::iterator it=open.begin(); it!=open.end(); it++)
			if(!pn || f(pn)>f(*it))
				pn=*it;

		open.erase(pn);
		closed.insert(pn);

		if(pn==to) // reach
		{
			list<node*> ret;
			ret.push_back(to);
			while(true)
			{
				node* nPrev=prev[ret.front()];
				if(!nPrev) break;
				ret.push_front(nPrev);
			}
			return ret;
		}

		int gn=g[pn];

		// adj
		list<node*> adjs=pn->getAdjs();
		for(list<node*>::iterator it=adjs.begin(); it!=adjs.end(); it++) // pa is in adj
		{
			node* padj=*it;
			if(closed.find(padj)!=closed.end())
				continue;

			open.insert(padj);
			g[padj]=gn+1;
		}

	}

	return list<node*>();

#undef f
#undef h
}

int main()
{
	return 0;
}